/*
 * Copyright 2011 Katsunori Koyanagi
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */

package sweezy.anim.util
{
	import flash.display.Graphics;
	import flash.geom.Matrix;
	import flash.geom.Point;
	import flash.geom.Rectangle;

	public class Path
	{

		private static const QUAD_TO_CUBIC_RATIO:Number = 2 / 3;

		private static var _xBounds:Array = [];

		private static var _yBounds:Array = [];

		private var _interpolate:uint;

		private var _lastX:Number;

		private var _lastY:Number;

		private var _open:Boolean;

		private var _segments:Array;

		private var _totalLength:Number;

		private var _x:Number;

		private var _y:Number;

		public function Path(interpolate:uint = 0)
		{
			_x = 0;
			_y = 0;
			_lastX = 0;
			_lastY = 0;
			_segments = [];
			_open = false;
			_interpolate = interpolate;
		}

		public function add(path:Path):void
		{
			if (path === null)
			{
				return;
			}

			add0(path, _segments.concat(path._segments));
		}

		public function applyMatrix(matrix:Matrix):void
		{
			if (matrix === null)
			{
				return;
			}

			var a:Number = matrix.a;
			var b:Number = matrix.b;
			var c:Number = matrix.c;
			var d:Number = matrix.d;
			var tx:Number = matrix.tx;
			var ty:Number = matrix.ty;
			var x:Number, y:Number;

			x = _x;
			y = _y;
			_x = x * a + y * c + tx;
			_y = x * b + y * d + ty;
			x = _lastX;
			y = _lastY;
			_lastX = x * a + y * c + tx;
			_lastY = x * b + y * d + ty;

			for (var i:int = 0, len:uint = _segments.length; i < len; i++)
			{
				(_segments[i] as Segment).applyMatrix(matrix);
			}
		}

		public function close():void
		{
			if (!_open)
			{
				return;
			}
			if (_x === _lastX && _y === _lastY)
			{
				return;
			}

			lineTo(_lastX, _lastY);
		}

		public function curveTo(controlX1:Number, controlY1:Number, controlX2:Number, controlY2:Number, anchorX:Number, anchorY:Number):void
		{
			addPath(2, anchorX, anchorY, controlX1, controlY1, controlX2, controlY2);
		}

		public function debug(g:Graphics):void
		{

			var segment:Segment;
			var point:Point = new Point();

			for (var i:int = 0, len:uint = _segments.length; i < len; i++)
			{
				segment = _segments[i] as Segment;
				g.moveTo(segment.sx, segment.sy);

				for (var j:int = 0; j <= 20; j++)
				{
					segment.pointForT(j / 20);
					g.lineTo(segment.px, segment.py);
				}
			}
		}

		public function getBounds(rect:Rectangle):void
		{
			if (rect === null)
			{
				return;
			}

			_xBounds.length = 0;
			_yBounds.length = 0;
			var segment:Segment;

			for (var i:int = 0, len:uint = _segments.length; i < len; i++)
			{
				(_segments[i] as Segment).findBounds(_xBounds, _yBounds);
			}

			rect.left = Math.min.apply(null, _xBounds);
			rect.right = Math.max.apply(null, _xBounds);
			rect.top = Math.min.apply(null, _yBounds);
			rect.bottom = Math.max.apply(null, _yBounds);
		}

		public function getLength():Number
		{
			if (isNaN(_totalLength))
			{
				_totalLength = 0;
				for (var i:int = 0, len:uint = _segments.length; i < len; i++)
				{
					_totalLength += (_segments[i] as Segment).len;
				}
			}

			return _totalLength;
		}

		public function lineTo(x:Number, y:Number):void
		{
			addPath(0, x, y, NaN, NaN, NaN, NaN);
		}

		public function moveTo(x:Number, y:Number):void
		{
			if (_x === x && _y === y)
			{
				return;
			}

			_x = x;
			_y = y;
			_lastX = x;
			_lastY = y;
		}

		public function pointForT(t:Number, point:Point):void
		{
			if (isNaN(t) || t < 0 || t > 1 || point === null)
			{
				return;
			}

			var target:Number = getLength() * t;
			var start:Number = 0;
			var end:Number = 0;
			var segment:Segment;

			for (var i:int = 0, len:uint = _segments.length; i < len; i++)
			{
				segment = _segments[i] as Segment;
				start = end;
				end += segment.len;

				if (start <= target && target <= end)
				{
					break;
				}
			}

			segment.pointForT(1 - (end - target) / segment.len);
			point.x = segment.px;
			point.y = segment.py;
		}

		public function quadTo(controlX:Number, controlY:Number, anchorX:Number, anchorY:Number):void
		{
			addPath(1, anchorX, anchorY, controlX, controlY, NaN, NaN);
		}

		public function split(t:Number, array:Array):int
		{
			if (isNaN(t) || t < 0 || t > 1 || array === null)
			{
				return 0;
			}

			var target:Number = getLength() * t;
			var start:Number = 0;
			var end:Number = 0;
			var segment:Segment;
			var index:int = 0;
			for (var i:int = 0, len:uint = _segments.length; i < len; i++)
			{
				index = i;
				segment = _segments[i] as Segment;
				start = end;
				end += segment.len;

				if (start <= target && target <= end)
				{
					break;
				}
			}

			t = 1 - (end - target) / segment.len;
			var path0:Path, path1:Path;

			if (t === 0)
			{
				if (index === 0)
				{
					path0 = new Path();
					path0.add(this);
					array[0] = path0;
					return 1;
				}
				else
				{
					path0 = new Path();
					path0.add0(this, _segments.slice(0, index));
					array[0] = path0;

					path1 = new Path();
					path1.add0(this, _segments.slice(index));
					array[1] = path1;

					return 2;
				}
			}
			else if (t === 1)
			{
				if (index === _segments.length - 1)
				{
					path0 = new Path();
					path0.add(this);
					array[0] = path0;
					return 1;
				}
				else
				{
					path0 = new Path();
					path0.add0(this, _segments.slice(0, index));
					array[0] = path0;

					path1 = new Path();
					path1.add0(this, _segments.slice(index));
					array[1] = path1;

					return 2;
				}
			}

			segment.split(t, array);

			var a:Array = _segments.slice(0, index);
			a.push(array[0]);
			path0 = new Path();
			path0.add0(this, a);

			a = _segments.slice(index + 1);
			a.unshift(array[1]);
			path1 = new Path();
			path1.add0(this, a);

			array[0] = path0;
			array[1] = path1;

			return 2;
		}

		private function add0(path:Path, infos:Array):void
		{
			_segments = infos;
			_totalLength = NaN;
			_x = path._x;
			_y = path._y;
			_lastX = path._lastX;
			_lastY = path._lastY;
			_open = path._open;
		}

		private function addPath(type:uint, endX:Number, endY:Number, cx1:Number, cy1:Number, cx2:Number, cy2:Number):void
		{
			var segment:Segment = type === 0 ? new StraightSegment() : new BezierSegment();
			segment.sx = _x;
			segment.sy = _y;
			segment.ex = endX;
			segment.ey = endY;

			if (type > 0)
			{
				var bsegment:BezierSegment = segment as BezierSegment;
				bsegment.interpolate = _interpolate === 0 ? 50 : _interpolate;

				if (type === 1)
				{
					bsegment.cx1 = _x + (cx1 - _x) * QUAD_TO_CUBIC_RATIO;
					bsegment.cy1 = _y + (cy1 - _y) * QUAD_TO_CUBIC_RATIO;
					bsegment.cx2 = endX + (cx1 - endX) * QUAD_TO_CUBIC_RATIO;
					bsegment.cy2 = endY + (cy1 - endY) * QUAD_TO_CUBIC_RATIO;
				}
				else
				{
					bsegment.cx1 = cx1;
					bsegment.cy1 = cy1;
					bsegment.cx2 = cx2;
					bsegment.cy2 = cy2;
				}
			}

			segment.computeLength();
			if (isNaN(segment.len))
			{
				return;
			}

			_segments[_segments.length] = segment;

			_x = endX;
			_y = endY;
			_open = !(_lastX === endX && _lastY === endY);
			_totalLength = NaN;
		}
	}
}

import flash.geom.Matrix;

class Segment
{

	public var ex:Number;

	public var ey:Number;

	public var len:Number;

	public var px:Number;

	public var py:Number;

	public var sx:Number;

	public var sy:Number;

	public function applyMatrix(matrix:Matrix):void
	{
	}

	public function computeLength():void
	{
	}

	public function findBounds(xBounds:Array, yBounds:Array):void
	{
	}

	public function pointForT(t:Number):void
	{
	}

	public function split(t:Number, array:Array):void
	{
	}
}

class BezierSegment extends Segment
{

	public var cx1:Number;

	public var cx2:Number;

	public var cy1:Number;

	public var cy2:Number;

	public var interpolate:uint;

	override public function applyMatrix(matrix:Matrix):void
	{
		var a:Number = matrix.a;
		var b:Number = matrix.b;
		var c:Number = matrix.c;
		var d:Number = matrix.d;
		var tx:Number = matrix.tx;
		var ty:Number = matrix.ty;
		var x:Number, y:Number;

		x = sx;
		y = sy;
		sx = x * a + y * c + tx;
		sy = x * b + y * d + ty;
		x = ex;
		y = ey;
		ex = x * a + y * c + tx;
		ey = x * b + y * d + ty;
		x = cx1;
		y = cy1;
		cx1 = x * a + y * c + tx;
		cy1 = x * b + y * d + ty;
		x = cx2;
		y = cy2;
		cx2 = x * a + y * c + tx;
		cy2 = x * b + y * d + ty;

		computeLength();
	}

	override public function computeLength():void
	{
		len = getBezierLength(0, 1);
	}

	override public function findBounds(xBounds:Array, yBounds:Array):void
	{
		xBounds[xBounds.length] = sx;
		yBounds[yBounds.length] = sy;
		xBounds[xBounds.length] = ex;
		yBounds[yBounds.length] = ey;

		var bx:Number = 6 * sx - 12 * cx1 + 6 * cx2;
		var by:Number = 6 * sy - 12 * cy1 + 6 * cy2;
		var ax:Number = -3 * sx + 9 * cx1 - 9 * cx2 + 3 * ex;
		var ay:Number = -3 * sy + 9 * cy1 - 9 * cx2 + 3 * ey;
		var cx:Number = 3 * cx1 - 3 * sx;
		var cy:Number = 3 * cy1 - 3 * sy;
		var x0:Number = cx1 - sx;
		var y0:Number = cy1 - sy;
		var x1:Number = cx2 - cx1 - x0;
		var y1:Number = cy2 - cy1 - y0;
		var x2:Number = ex - cx2 - x1 - cx2 + cx1;
		var y2:Number = ey - cy2 - y1 - cy2 + cy1;
		var t:Number;

		if (ax === 0)
		{
			if (bx !== 0)
			{
				t = -cx / bx;
				if (0 < t && t < 1)
				{
					xBounds[xBounds.length] = x2 * t * t * t + 3 * x1 * t * t + 3 * x0 * t + sx;
				}
			}
		}
		else
		{
			var b2acx:Number = bx * bx - 4 * cx * ax;
			if (b2acx >= 0)
			{
				t = (-bx + Math.sqrt(b2acx)) / (ax * 2);
				if (0 < t && t < 1)
				{
					xBounds[xBounds.length] = x2 * t * t * t + 3 * x1 * t * t + 3 * x0 * t + sx;
				}
				t = (-bx - Math.sqrt(b2acx)) / (ax * 2);
				if (0 < t && t < 1)
				{
					xBounds[xBounds.length] = x2 * t * t * t + 3 * x1 * t * t + 3 * x0 * t + sx;
				}
			}
		}

		if (ay === 0)
		{
			if (by !== 0)
			{
				t = -cy / by;
				if (0 < t && t < 1)
				{
					yBounds[yBounds.length] = y2 * t * t * t + 3 * y1 * t * t + 3 * y0 * t + sy;
				}
			}
		}
		else
		{
			var b2acy:Number = by * by - 4 * cy * ay;
			if (b2acy >= 0)
			{
				t = (-by + Math.sqrt(b2acy)) / (ay * 2);
				if (0 < t && t < 1)
				{
					yBounds[yBounds.length] = y2 * t * t * t + 3 * y1 * t * t + 3 * y0 * t + sy;
				}
				t = (-by - Math.sqrt(b2acy)) / (ay * 2);
				if (0 < t && t < 1)
				{
					yBounds[yBounds.length] = y2 * t * t * t + 3 * y1 * t * t + 3 * y0 * t + sy;
				}
			}
		}
	}

	override public function pointForT(t:Number):void
	{
		var x0:Number = cx1 - sx;
		var y0:Number = cy1 - sy;
		var x1:Number = cx2 - cx1 - x0;
		var y1:Number = cy2 - cy1 - y0;
		var x2:Number = ex - cx2 - x1 - cx2 + cx1;
		var y2:Number = ey - cy2 - y1 - cy2 + cy1;

		t = getCoordFromLength(len * t);
		px = x2 * t * t * t + 3 * x1 * t * t + 3 * x0 * t + sx;
		py = y2 * t * t * t + 3 * y1 * t * t + 3 * y0 * t + sy;
	}

	override public function split(t:Number, array:Array):void
	{
		var info0:BezierSegment = new BezierSegment();
		var info1:BezierSegment = new BezierSegment();

		info0.interpolate = interpolate;
		info1.interpolate = interpolate;
		info0.sx = sx;
		info1.ex = ex;
		info0.sy = sy;
		info1.ey = ey;

		t = 1 - getCoordFromLength(len * t);
		var x:Number = cx2 + (cx1 - cx2) * t;
		var y:Number = cy2 + (cy1 - cy2) * t;
		info0.cx1 = cx1 + (sx - cx1) * t;
		info0.cy1 = cy1 + (sy - cy1) * t;
		info1.cx2 = ex + (cx2 - ex) * t;
		info1.cy2 = ey + (cy2 - ey) * t;
		info0.cx2 = x + (info0.cx1 - x) * t;
		info0.cy2 = y + (info0.cy1 - y) * t;
		info1.cx1 = info1.cx2 + (x - info1.cx2) * t;
		info1.cy1 = info1.cy2 + (y - info1.cy2) * t;
		info0.ex = info1.sx = info1.cx1 + (info0.cx2 - info1.cx1) * t;
		info0.ey = info1.sy = info1.cy1 + (info0.cy2 - info1.cy1) * t;

		info0.computeLength();
		info1.computeLength();
		array[0] = info0;
		array[1] = info1;
	}

	private function getBezierLength(ta:Number, tb:Number):Number
	{
		var t:Number, x:Number, y:Number, ft:Number;
		var t2:Number = (tb - ta) / (2 * interpolate);
		var x0:Number = cx1 - sx;
		var y0:Number = cy1 - sy;
		var x1:Number = cx2 - cx1 - x0;
		var y1:Number = cy2 - cy1 - y0;
		var x2:Number = ex - cx2 - x1 - cx2 + cx1;
		var y2:Number = ey - cy2 - y1 - cy2 + cy1;

		x = 3 * (x2 * ta * ta + 2 * x1 * ta + x0);
		y = 3 * (y2 * ta * ta + 2 * y1 * ta + y0);
		ft = Math.sqrt(x * x + y * y);

		x = 3 * (x2 * tb * tb + 2 * x1 * tb + x0);
		y = 3 * (y2 * tb * tb + 2 * y1 * tb + y0);
		ft += Math.sqrt(x * x + y * y);

		for (var i:int = 1; i <= interpolate; i++)
		{
			t = ta + (2 * i - 1) * t2;
			x = 3 * (x2 * t * t + 2 * x1 * t + x0);
			y = 3 * (y2 * t * t + 2 * y1 * t + y0);
			ft += Math.sqrt(x * x + y * y) * 4;

			t = ta + 2 * i * t2;
			x = 3 * (x2 * t * t + 2 * x1 * t + x0);
			y = 3 * (y2 * t * t + 2 * y1 * t + y0);
			ft += i < interpolate ? Math.sqrt(x * x + y * y) * 2 : 0;
		}

		return t2 / 3 * ft;
	}

	private function getCoordFromLength(len:Number):Number
	{
		var x:Number, y:Number, v:Number, v2:Number;
		var t:Number = 1, d:Number = 0;
		var x0:Number = cx1 - sx;
		var y0:Number = cy1 - sy;
		var x1:Number = cx2 - cx1 - x0;
		var y1:Number = cy2 - cy1 - y0;
		var x2:Number = ex - cx2 - x1 - cx2 + cx1;
		var y2:Number = ey - cy2 - y1 - cy2 + cy1;

		if (len === 0)
		{
			return 0;
		}
		else if (len >= this.len)
		{
			return 1;
		}

		t = len / this.len;
		while (true)
		{
			v2 = getBezierLength(0, t);
			v = ((v = v2 - len) < 0 ? -v : v) / len;
			if (v <= 0.000001)
			{
				break;
			}

			x = 3 * (x2 * t * t + 2 * x1 * t + x0);
			y = 3 * (y2 * t * t + 2 * y1 * t + y0);
			d += x * x + y * y;
			t += (len - v2) / Math.sqrt(d);
		}

		return t;
	}
}


class StraightSegment extends Segment
{

	override public function applyMatrix(matrix:Matrix):void
	{
		var a:Number = matrix.a;
		var b:Number = matrix.b;
		var c:Number = matrix.c;
		var d:Number = matrix.d;
		var tx:Number = matrix.tx;
		var ty:Number = matrix.ty;
		var x:Number, y:Number;

		x = sx;
		y = sy;
		sx = x * a + y * c + tx;
		sy = x * b + y * d + ty;
		x = ex;
		y = ey;
		ex = x * a + y * c + tx;
		ey = x * b + y * d + ty;

		computeLength();
	}

	override public function computeLength():void
	{
		len = Math.sqrt((sx - ex) * (sx - ex) + (sy - ey) * (sy - ey));
	}

	override public function findBounds(xBounds:Array, yBounds:Array):void
	{
		xBounds[xBounds.length] = sx;
		yBounds[yBounds.length] = sy;
		xBounds[xBounds.length] = ex;
		yBounds[yBounds.length] = ey;
	}

	override public function pointForT(t:Number):void
	{
		px = sx + (ex - sx) * t;
		py = sy + (ey - sy) * t;
	}

	override public function split(t:Number, array:Array):void
	{
		var info0:StraightSegment = new StraightSegment();
		var info1:StraightSegment = new StraightSegment();

		info0.sx = sx;
		info1.ex = ex;
		info0.sy = sy;
		info1.ey = ey;
		info0.ex = info1.sx = sx + (ex - sx) * t;
		info0.ey = info1.sy = sy + (ey - sy) * t;

		info0.computeLength();
		info1.computeLength();
		array[0] = info0;
		array[1] = info1;
	}
}
